#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include "../1027/seqstack/stack.h"

char *converse_mid(const char *p);

int main(int argc, char *argv[])
{
	char *ret = NULL;

	if (argc < 2)
		return 1;

	ret = converse_mid(argv[1]);
	if (NULL == ret)
		return 1;
	puts(ret);
	free(ret);
	ret = NULL;

	return 0;
}

static int is_digital(char c)
{
	return c >= '0' && c <= '9';
}

static int is_operator(char c)
{
	return c == '+' || c == '-' || c == '*' || c == '/';
}

static int operator_level(char c)
{
	int level = 0;
	
	if (c == '*' || c == '/')
		level = 2;
	else if (c == '+' || c == '-')
		level = 1;

	return level;
}

char *converse_mid(const char *p)
{
	stack_t *res, *op;//结果栈 运算符栈
	size_t len;//字符串p长度
	int i;//控制字符串入栈
	char tmp;//存放字符串出栈比较
	char *ptr = NULL;//存放结果前缀表达式

	len = strlen(p);

	stack_init(&res, sizeof(char), len);
	stack_init(&op, sizeof(char), len);
	
	i = len - 1;
	while (i >= 0) {
		if (is_digital(p[i]))
			stack_push(res, p + i);
		else if (p[i] == ')')
			stack_push(op, p + i);
		else if (is_operator(p[i])) {
			while (!stack_empty(op)) {
				stack_pop(op, &tmp);
				if (operator_level(p[i]) < operator_level(tmp)) {// 弹出来的高才能放结果栈
					stack_push(res, &tmp);
				} else {
					stack_push(op, &tmp);//弹出来的小于等于  那只能继续放进去 结束本循环
					break;
				}
			}
			stack_push(op, p + i);
		} else if (p[i] == '(') {
			while (!stack_empty(op)) {
				stack_pop(op, &tmp);
				if (tmp == ')')
					break;
				stack_push(res, &tmp);
			}
			if (tmp != ')')
				goto ERROR;
		} else {
			goto ERROR;
		}
		i--;
	}

	while (!stack_empty(op)) {
		stack_pop(op, &tmp);
		stack_push(res, &tmp);
	}

	ptr = malloc(len + 1);	
	i = 0;
	while (!stack_empty(res)) {
		stack_pop(res, ptr + i);
		i++;
	}
	ptr[i] = '\0';

	stack_destroy(&res);
	stack_destroy(&op);

	return ptr;
ERROR:
	stack_destroy(&res);
	stack_destroy(&op);
	return NULL;
}






